All Write-ups
Cryptography
Cryptography

Crack the Power

We received an encrypted message. The modulus is built from primes large enough that factoring them isn't an option, at least not today. See if you can make sense of the numbers and reveal the flag.

Crack the Power

We received an encrypted message. The modulus is built from primes large enough that factoring them isn't an option, at least not today. See if you can make sense of the numbers and reveal the flag.

Information Given

Description

We received an encrypted message. The modulus is built from primes large enough that factoring them isn't an option, at least not today. See if you can make sense of the numbers and reveal the flag.

Download the message.

Hints

  • • When certain values in the encryption setup are smaller than usual, it opens up unexpected shortcuts to recover the plaintext
  • • Consider whether you can invert the encryption without factoring n
  • • Read more about Coppersmith's attack

Message

We received an encrypted message. See if you can make sense of the numbers and reveal the flag.

We are given:

We're given an RSA encrypted message with the following parameters:

  • • n: A very large 2048-bit modulus
  • • e: 20 (unusually small public exponent)
  • • c: The ciphertext
n = 410664186165191791402826020648772079727855370225121168329489558023676206903110917122249911944501914058167574154300515578639528319920053023867482073692484985287827372248686968550452147219495058219737726533198589146788106207104006141113375574066854852611259725786317821883172497842657985257908701482139090568993822965683214349918502719101583356882168338270447984584381812927858227415072514189838197665563968909219013964220237934124402478909876364171409578837503118525132848891505287317986848688438750873278654357181872934401664809196436196103395671068981692006881025785118124735403009761732676194557783341186696317289217601680762240946756099165359859285900990663149297784065325172930606950668533524438921457116354261722563783316401034088432522913099965625002265981169229586378601077820521982226216733874547440407450338648780337291742094848216093949046938054996321130253196977418170117347647315719448397122004966163394965123751185910309725139116961163368621449406198577849587926254211380551265442088456309106778455980283046226445371066856262215933615411567261989837352437927401685169541910706297673710978352664847844643089079402646094504545790754030992062817610552755382423490304761138904591244735268207666957111641348148546651263055711

e = 20

c = 640637430810406857500566702096274079868087131935153057078985716461078483409793615804311883296591203324452249008450521032645267345512046769994383635285244380705157432625570066632528925314552900669814963219369331313157534607620352061314683496525883016843153241425770911702563380247302073740850825452371063276867610414725164654421304873071774234683226777641240092032528116047489137507373500064099947304524782898265669628686091404044097235795818651902023996906668123465373292221934136216954999213086853380479136606214034827032162211811911299453884553459883192781319337391984912950371275232374262114220706295073924345743106413419931715570201067076471272561731959500262271837841417300230554359594018424813861589485400512131504027368400263321851762034719595379735999122340323973277638235482616225404363214027767922993075345559200374830345517529445328472713066257434684134913873359589576414681791333170123047390862933633440111883394760439698156048278154619895786259579727797488066274962774692244105308866923365722966155030681035814505674226605348055192323888099731031683511808581367884577911318683020417249790405911629045010877656025044271667195964670746001

Solve Script

from gmpy2 import iroot

# Given values
n = 410664186165191791402826020648772079727855370225121168329489558023676206903110917122249911944501914058167574154300515578639528319920053023867482073692484985287827372248686968550452147219495058219737726533198589146788106207104006141113375574066854852611259725786317821883172497842657985257908701482139090568993822965683214349918502719101583356882168338270447984584381812927858227415072514189838197665563968909219013964220237934124402478909876364171409578837503118525132848891505287317986848688438750873278654357181872934401664809196436196103395671068981692006881025785118124735403009761732676194557783341186696317289217601680762240946756099165359859285900990663149297784065325172930606950668533524438921457116354261722563783316401034088432522913099965625002265981169229586378601077820521982226216733874547440407450338648780337291742094848216093949046938054996321130253196977418170117347647315719448397122004966163394965123751185910309725139116961163368621449406198577849587926254211380551265442088456309106778455980283046226445371066856262215933615411567261989837352437927401685169541910706297673710978352664847844643089079402646094504545790754030992062817610552755382423490304761138904591244735268207666957111641348148546651263055711

e = 20

c = 640637430810406857500566702096274079868087131935153057078985716461078483409793615804311883296591203324452249008450521032645267345512046769994383635285244380705157432625570066632528925314552900669814963219369331313157534607620352061314683496525883016843153241425770911702563380247302073740850825452371063276867610414725164654421304873071774234683226777641240092032528116047489137507373500064099947304524782898265669628686091404044097235795818651902023996906668123465373292221934136216954999213086853380479136606214034827032162211811911299453884553459883192781319337391984912950371275232374262114220706295073924345743106413419931715570201067076471272561731959500262271837841417300230554359594018424813861589485400512131504027368400263321851762034719595379735999122340323973277638235482616225404363214027767922993075345559200374830345517529445328472713066257434684134913873359589576414681791333170123047390862933633440111883394760439698156048278154619895786259579727797488066274962774692244105308866923365722966155030681035814505674226605348055192323888099731031683511808581367884577911318683020417249790405911629045010877656025044271667195964670746001

# Direct root extraction attack
m, is_exact_root = iroot(c, e)

if is_exact_root:
    # Convert to bytes and decode
    flag_bytes = m.to_bytes((m.bit_length() + 7) // 8, 'big')
    flag = flag_bytes.decode('ascii')
    print(f"Flag: {flag}")
else:
    print("Direct root failed - would need Coppersmith's attack")

To be able to run this:

pip install gmpy2

This leaves us with the flag: picoCTF{t1ny_e_381870dd}

The Flag

picoCTF{'{'}t1ny_e_381870dd}